from typing import List


def bsearch_loop(array: List, target:int) -> int:
    """
    从顺序数组进行二分查找
    :param array:
    :param target:
    :return:
    """
    low, high = 0, len(array) -1
    while low <= high:
        mid = low + (high - low)//2
        if array[mid] > target:
            high = mid-1
        elif array[mid] < target:
            low = mid+1
        else:
            return mid
    return -1


def _bsearch_recur(array, target, low, high):
    if low > high:
        return -1

    mid = low + (high-low)//2
    if array[mid] == target:
        return mid
    if array[mid] > target:
        return _bsearch_recur(array, target, low, mid-1)
    else:
        return _bsearch_recur(array, target, mid+1, high)


def bsearch_recusive(array: List, target:int) -> int:
    return _bsearch_recur(array, target, 0, len(array)-1)


def bsearch_left(array: List, target:int) -> int:
    """
    查找第一个值等于给定值的元素
    :param array:
    :param target:
    :return:
    """
    low = 0
    high = len(array)-1
    while low  <= high:
        mid = low + (high-low)//2
        if array[mid] > target:
            high = mid - 1
        elif array[mid] < target:
            low = mid + 1
        else:
            if mid==0 or array[mid-1] != target:
                return mid
            else:
                high = mid-1
    return -1


def bsearch_left_no_less(array: List, target:int) -> int:
    """
    查找第一个值大于等于给定值的元素
    :param array:
    :param target:
    :return:
    """
    low = 0
    high = len(array)-1
    while low <= high:
        mid = low + (high-low)//2
        if array[mid] >= target:
            if mid==0 or array[mid-1]<target:
                return mid
            else:
                high = mid-1
        else:
            low = mid + 1
    return -1


def bsearch_right(array: List, target:int) -> int:
    """
    查找最后一个值等于给定值的元素
    :param array:
    :param target:
    :return:
    """
    low = 0
    high = len(array) - 1
    while low <= high:
        mid = low + (high-low)//2
        if array[mid] > target:
            high = mid - 1
        elif array[mid] < target:
            low = mid + 1
        else:
            if mid == len(array)-1 or array[mid+1] != target:
                return mid
            else:
                low = mid + 1
    return -1


def bsearch_right_not_greater(array: List, target:int) -> int:
    """
    查找最后一个值小于等于给定值的元素
    :param array:
    :param target:
    :return:
    """
    low = 0
    high = len(array)-1
    while low <= high:
        mid = low + (high-low)//2
        if array[mid] <= target:
            if mid == len(array)-1 or array[mid+1] > target:
                return mid
            else:
                low = mid+1
        else:
            high = mid -1


if __name__ == '__main__':
    array = [0, 1, 6, 8, 12,12, 20, 34, 50, 56, 78, 120, 120, 120, 300, 1000]
    print(array)
    print("binary search loop: ", array[bsearch_loop(array, target=1)])
    print("binary search recursive: ", array[bsearch_recusive(array, target=1)])

    print("查找第一个等于目标值的元素的位置: ", bsearch_left(array, target=120))
    print("查找最后一个等于目标值的元素的位置：", bsearch_right(array, target=120))
    print("查找第一个值大于等于给定值的元素的位置: ", bsearch_left_no_less(array, target=120))
    print("查查找最后一个值小于等于给定值的元素的位置: ", bsearch_right_not_greater(array, target=120))
